1. Field of the Invention
The present invention relates to a range-finding circuit, and more particularly to a range-finding circuit using carry lookahead cells arranged in a circular hierarchical order.
2. Description of the Related Art
Processors generally process a single instruction in several steps. Early technology processors performed these steps serially. Advances in technology have led to pipelined-architecture processors, which may be called scalar processors, which perform different steps of many instructions concurrently. A "superscalar" processor is implemented using a pipelined structure, but further improves performance by supporting concurrent execution of scalar instructions.
In a superscalar processor, instruction conflicts and dependency conditions arise in which an issued instruction cannot be executed because necessary data or resources are not available. For example, an issued instruction cannot execute when its input operands are dependent upon data calculated by other instructions that have not yet completed execution. One method for handling data dependencies uses a buffer to temporarily hold information identifying operands for which data is unavailable. The buffer checks for data dependencies by comparing input operands to all of the temporarily held operands.
Superscalar processor performance is improved by the speculative execution of instructions and by continuing to decode instructions regardless of the ability to execute instructions immediately. One technique for decoupling instruction execution from instruction decoding uses a buffer to temporarily hold information relating to instructions in a speculative state.
The buffer also improves the processor's performance of instruction sequences that include interspersed branch instructions. Branch instructions impair processor performance because instructions following the branch commonly must wait for a condition to become known before execution may proceed. A superscalar processor improves branching performance by "speculatively" issuing instructions, which involves predicting the outcome of a branch condition and proceeding with subsequent instructions in accordance with the prediction. The buffer is implemented to maintain the speculative state of the processor. When a misprediction occurs, the buffer is flushed.
In addition, various buffer implementations facilitate a processor's recovery from interrupts or traps arising from illegal instructions, preset trace operations, programmed stopping points, memory errors and other causes. The processor prepares for an interrupt or trap by storing manifestations of current conditions, processor state, and the address of the current instructions in the buffer. After completing a trap or interrupt routine, the processor returns to normal execution of the instruction stream, based on the stored data. Because interrupts and traps may occur at any point in an instruction sequence, the buffer must monitor the instruction stream to properly suspend and restart instruction execution.
One buffer, which may be called a reorder buffer, may furnish all of these functions. The performance requirements of the buffer are demanding and are increasingly burdensome as the number of buffer entries is expanded. For example, dependency checking requires that each input operand be compared to every reorder buffer entry and the comparison must be done in an instant. Furthermore, when a branch is mispredicted, the buffer must immediately identify buffer entries within the mispredicted branch path.
What is needed is a reorder buffer which quickly checks for data dependencies and buffer entries in a mispredicted branch path. What is needed is a dependency checking circuit for usage in a reorder buffer which instantaneously checks for data dependencies between one or more input operands and numerous unavailable and speculative operands. What is needed is a range-finding circuit for usage in reorder buffers and dependency checking circuits which immediately enables a range of bits identified by a two pointers.